package com.sicheng.algorithm.dynamic;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/10/6 20:14
 */
@SuppressWarnings("unused")
public class Bag {
    public static void main(String[] args) {

        int[] weights = {2, 3, 5, 5};
        int[] values = {2, 4, 3, 7};

        int maxValue = knapsack(7, weights, values);
        System.err.println(maxValue);
    }

    /**
     * 有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。
     * <p>
     * 定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：
     * <p>
     * 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
     * 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。
     * 第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
     * <p>
     * //如果第i个物品质量大于当前背包容量
     * if (wt[i] > W) {
     * dp[i][W] = dp[i-1][W];  //继承上一个结果
     * } else {
     * //在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
     * dp[i][W] = Math.max(dp[i-1][W],dp[i-1][W-wt[i]] + val[i])
     * }
     */
    public static int knapsack(int N, int[] weights, int[] values) {
        if (weights == null ||
                weights.length == 0 ||
                values == null ||
                values.length == 0 ||
                N <= 0)
            return 0;
        int[] dp = new int[N + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int j = dp.length - 1; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        return dp[N];
    }
}
